图灵奖正式揭晓！史上首位数学和计算机最高奖“双料王”诞生

昨天晚间计算机协会ACM宣布，将“计算机界最高荣誉”图灵奖授予复杂性理论先驱、普林斯顿高等研究院教授艾维·维格森（Avi Wigderson）。

维格森教授在2021年还获得了被誉为“数学界诺贝尔奖”的阿贝尔奖，其也成为首个同时拿下数学和计算机最高奖的科学家。

值得一提的是，他还是2017年阿里达摩院刚成立时首批“十大祖师”之一

ACM表示，这是对维格森教授在计算理论的基础性贡献，包括塑造对计算中随机性作用的理解，以及数十年来在理论计算机科学领域卓越领导力的表彰。

作为一名数学家和计算机科学家，维格森在计算复杂性理论、算法和优化、随机性和密码学、并行和分布式计算、组合学、图论以及理论计算机科学与数学、科学之间的关联等领域都是领军学者。

维格森最重要的贡献，就是增强了人类对计算中随机性和伪随机性作用的理解。

简单来说，20世纪70年代末，科学家们发现对于许多难题，采用随机性的算法（也称为概率算法）可以远远胜过其确定性方案。

而在20世纪80年代，维格森与Richard Karp合作，发现了一种针对某个难题的随机算法，然后发现：能够将其去随机化，从而有效地揭示了它的确定性算法。

在1994年，维格森和Noam Nisan证明，如果存在任何自然难题，那么每一种有效的随机算法都可以被有效的确定性算法所取代。

更重要的是，他们还发现确定性算法可能使用“伪随机”序列——也就是看似随机但实际上并非随机的数据串。

这一系列研究彻底改变了计算机科学家对随机性的看法，并适用于理论计算机科学的许多领域。

ACM将图灵奖这一重要荣誉颁给了维格森，主要嘉奖的就是他在如上领域的贡献。